/*
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */

/*
 *
 *
 *
 *
 *
 * Written by Doug Lea with assistance from members of JCP JSR-166
 * Expert Group and released to the public domain, as explained at
 * http://creativecommons.org/publicdomain/zero/1.0/
 */

package net.vinote.smart.socket.lang;

import java.lang.ref.WeakReference;
import java.nio.ByteBuffer;
import java.util.AbstractQueue;
import java.util.Collection;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Spliterator;
import java.util.Spliterators;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;

/**
 * A bounded {@linkplain BlockingQueue blocking queue} backed by an array. This
 * queue orders elements FIFO (first-in-first-out). The <em>head</em> of the
 * queue is that element that has been on the queue the longest time. The
 * <em>tail</em> of the queue is that element that has been on the queue the
 * shortest time. New elements are inserted at the tail of the queue, and the
 * queue retrieval operations obtain elements at the head of the queue.
 *
 * <p>
 * This is a classic &quot;bounded buffer&quot;, in which a fixed-sized array
 * holds elements inserted by producers and extracted by consumers. Once
 * created, the capacity cannot be changed. Attempts to {@code put} an element
 * into a full queue will result in the operation blocking; attempts to
 * {@code take} an element from an empty queue will similarly block.
 *
 * <p>
 * This class supports an optional fairness policy for ordering waiting producer
 * and consumer threads. By default, this ordering is not guaranteed. However, a
 * queue constructed with fairness set to {@code true} grants threads access in
 * FIFO order. Fairness generally decreases throughput but reduces variability
 * and avoids starvation.
 *
 * <p>
 * This class and its iterator implement all of the <em>optional</em> methods of
 * the {@link Collection} and {@link Iterator} interfaces.
 *
 * <p>
 * This class is a member of the <a href=
 * "{@docRoot}/../technotes/guides/collections/index.html"> Java Collections
 * Framework</a>.
 *
 * @since 1.5
 * @author Doug Lea
 * @param <E>
 *            the type of elements held in this collection
 */
public class ArrayBlockingQueue extends AbstractQueue<ByteBuffer>
	implements BlockingQueue<ByteBuffer>, java.io.Serializable {

	/**
	 * Serialization ID. This class relies on default serialization even for the
	 * items array, which is default-serialized, even if it is empty. Otherwise
	 * it could not be declared final, which is necessary here.
	 */
	private static final long serialVersionUID = -817911632652898426L;

	/** The queued items */
	final ByteBuffer[] items;

	/** items index for next take, poll, peek or remove */
	int takeIndex;

	/** items index for next put, offer, or add */
	int putIndex;

	/** Number of elements in the queue */
	int count;

	/*
	 * Concurrency control uses the classic two-condition algorithm found in any
	 * textbook.
	 */

	/** Main lock guarding all access */
	final ReentrantLock lock;

	/** Condition for waiting takes */
	private final Condition notEmpty;

	/** Condition for waiting puts */
	private final Condition notFull;

	/**
	 * Shared state for currently active iterators, or null if there are known
	 * not to be any. Allows queue operations to update iterator state.
	 */
	transient Itrs itrs = null;

	// Internal helper methods

	/**
	 * Circularly decrement i.
	 */
	final int dec(int i) {
		return ((i == 0) ? items.length : i) - 1;
	}

	/**
	 * Returns item at index i.
	 */
	final ByteBuffer itemAt(int i) {
		return items[i];
	}

	/**
	 * Throws NullPointerException if argument is null.
	 *
	 * @param v
	 *            the element
	 */
	private static void checkNotNull(Object v) {
		if (v == null)
			throw new NullPointerException();
	}

	/**
	 * Inserts element at current put position, advances, and signals. Call only
	 * when holding lock.
	 */
	private void enqueue(ByteBuffer x) {
		// assert lock.getHoldCount() == 1;
		// assert items[putIndex] == null;
		final ByteBuffer[] items = this.items;
		// 压缩bytebuffer
		ByteBuffer preBuffer = null;
		if (count > 1) {// 存在两个元素才进行压缩
			int index = putIndex - 1;
			if (index < 0) {
				index = items.length - 1;
			}
			preBuffer = items[index];
		}
		if (preBuffer != null && preBuffer.capacity() > preBuffer.limit()) {
			preBuffer.position(preBuffer.limit());
			preBuffer.limit(preBuffer.capacity());
			while (preBuffer.hasRemaining() && x.hasRemaining()) {
				preBuffer.put(x.get());
			}
			preBuffer.flip();
			// preBuffer.limit(preBuffer.capacity() - num);
			if (x.hasRemaining()) {
				x.compact();
				x.flip();
			} else {
				return;
			}
		}

		items[putIndex] = x;
		if (++putIndex == items.length)
			putIndex = 0;
		count++;
		notEmpty.signal();
	}

	/**
	 * Extracts element at current take position, advances, and signals. Call
	 * only when holding lock.
	 */
	private ByteBuffer dequeue() {
		// assert lock.getHoldCount() == 1;
		// assert items[takeIndex] != null;
		final ByteBuffer[] items = this.items;
		ByteBuffer x = items[takeIndex];
		items[takeIndex] = null;
		if (++takeIndex == items.length)
			takeIndex = 0;
		count--;
		if (itrs != null)
			itrs.elementDequeued();
		notFull.signal();
		return x;
	}

	/**
	 * Deletes item at array index removeIndex. Utility for remove(Object) and
	 * iterator.remove. Call only when holding lock.
	 */
	void removeAt(final int removeIndex) {
		// assert lock.getHoldCount() == 1;
		// assert items[removeIndex] != null;
		// assert removeIndex >= 0 && removeIndex < items.length;
		final Object[] items = this.items;
		if (removeIndex == takeIndex) {
			// removing front item; just advance
			items[takeIndex] = null;
			if (++takeIndex == items.length)
				takeIndex = 0;
			count--;
			if (itrs != null)
				itrs.elementDequeued();
		} else {
			// an "interior" remove

			// slide over all others up through putIndex.
			final int putIndex = this.putIndex;
			for (int i = removeIndex;;) {
				int next = i + 1;
				if (next == items.length)
					next = 0;
				if (next != putIndex) {
					items[i] = items[next];
					i = next;
				} else {
					items[i] = null;
					this.putIndex = i;
					break;
				}
			}
			count--;
			if (itrs != null)
				itrs.removedAt(removeIndex);
		}
		notFull.signal();
	}

	/**
	 * Creates an {@code ArrayBlockingQueue} with the given (fixed) capacity and
	 * default access policy.
	 *
	 * @param capacity
	 *            the capacity of this queue
	 * @throws IllegalArgumentException
	 *             if {@code capacity < 1}
	 */
	public ArrayBlockingQueue(int capacity) {
		this(capacity, false);
	}

	/**
	 * Creates an {@code ArrayBlockingQueue} with the given (fixed) capacity and
	 * the specified access policy.
	 *
	 * @param capacity
	 *            the capacity of this queue
	 * @param fair
	 *            if {@code true} then queue accesses for threads blocked on
	 *            insertion or removal, are processed in FIFO order; if
	 *            {@code false} the access order is unspecified.
	 * @throws IllegalArgumentException
	 *             if {@code capacity < 1}
	 */
	public ArrayBlockingQueue(int capacity, boolean fair) {
		if (capacity <= 0)
			throw new IllegalArgumentException();
		this.items = new ByteBuffer[capacity];
		lock = new ReentrantLock(fair);
		notEmpty = lock.newCondition();
		notFull = lock.newCondition();
	}

	/**
	 * Creates an {@code ArrayBlockingQueue} with the given (fixed) capacity,
	 * the specified access policy and initially containing the elements of the
	 * given collection, added in traversal order of the collection's iterator.
	 *
	 * @param capacity
	 *            the capacity of this queue
	 * @param fair
	 *            if {@code true} then queue accesses for threads blocked on
	 *            insertion or removal, are processed in FIFO order; if
	 *            {@code false} the access order is unspecified.
	 * @param c
	 *            the collection of elements to initially contain
	 * @throws IllegalArgumentException
	 *             if {@code capacity} is less than {@code c.size()}, or less
	 *             than 1.
	 * @throws NullPointerException
	 *             if the specified collection or any of its elements are null
	 */
	public ArrayBlockingQueue(int capacity, boolean fair, Collection<? extends ByteBuffer> c) {
		this(capacity, fair);

		final ReentrantLock lock = this.lock;
		lock.lock(); // Lock only for visibility, not mutual exclusion
		try {
			int i = 0;
			try {
				for (ByteBuffer e : c) {
					checkNotNull(e);
					items[i++] = e;
				}
			} catch (ArrayIndexOutOfBoundsException ex) {
				throw new IllegalArgumentException();
			}
			count = i;
			putIndex = (i == capacity) ? 0 : i;
		} finally {
			lock.unlock();
		}
	}

	/**
	 * Inserts the specified element at the tail of this queue if it is possible
	 * to do so immediately without exceeding the queue's capacity, returning
	 * {@code true} upon success and throwing an {@code IllegalStateException}
	 * if this queue is full.
	 *
	 * @param e
	 *            the element to add
	 * @return {@code true} (as specified by {@link Collection#add})
	 * @throws IllegalStateException
	 *             if this queue is full
	 * @throws NullPointerException
	 *             if the specified element is null
	 */
	public boolean add(ByteBuffer e) {
		return super.add(e);
	}

	/**
	 * Inserts the specified element at the tail of this queue if it is possible
	 * to do so immediately without exceeding the queue's capacity, returning
	 * {@code true} upon success and {@code false} if this queue is full. This
	 * method is generally preferable to method {@link #add}, which can fail to
	 * insert an element only by throwing an exception.
	 *
	 * @throws NullPointerException
	 *             if the specified element is null
	 */
	public boolean offer(ByteBuffer e) {
		checkNotNull(e);
		final ReentrantLock lock = this.lock;
		lock.lock();
		try {
			if (count == items.length)
				return false;
			else {
				enqueue(e);
				return true;
			}
		} finally {
			lock.unlock();
		}
	}

	/**
	 * Inserts the specified element at the tail of this queue, waiting for
	 * space to become available if the queue is full.
	 *
	 * @throws InterruptedException
	 *             {@inheritDoc}
	 * @throws NullPointerException
	 *             {@inheritDoc}
	 */
	public void put(ByteBuffer e) throws InterruptedException {
		checkNotNull(e);
		final ReentrantLock lock = this.lock;
		lock.lockInterruptibly();
		try {
			while (count == items.length)
				notFull.await();
			enqueue(e);
		} finally {
			lock.unlock();
		}
	}

	/**
	 * Inserts the specified element at the tail of this queue, waiting up to
	 * the specified wait time for space to become available if the queue is
	 * full.
	 *
	 * @throws InterruptedException
	 *             {@inheritDoc}
	 * @throws NullPointerException
	 *             {@inheritDoc}
	 */
	public boolean offer(ByteBuffer e, long timeout, TimeUnit unit) throws InterruptedException {

		checkNotNull(e);
		long nanos = unit.toNanos(timeout);
		final ReentrantLock lock = this.lock;
		lock.lockInterruptibly();
		try {
			while (count == items.length) {
				if (nanos <= 0)
					return false;
				nanos = notFull.awaitNanos(nanos);
			}
			enqueue(e);
			return true;
		} finally {
			lock.unlock();
		}
	}

	public ByteBuffer poll() {
		final ReentrantLock lock = this.lock;
		lock.lock();
		try {
			return (count == 0) ? null : dequeue();
		} finally {
			lock.unlock();
		}
	}

	public ByteBuffer take() throws InterruptedException {
		final ReentrantLock lock = this.lock;
		lock.lockInterruptibly();
		try {
			while (count == 0)
				notEmpty.await();
			return dequeue();
		} finally {
			lock.unlock();
		}
	}

	public ByteBuffer poll(long timeout, TimeUnit unit) throws InterruptedException {
		long nanos = unit.toNanos(timeout);
		final ReentrantLock lock = this.lock;
		lock.lockInterruptibly();
		try {
			while (count == 0) {
				if (nanos <= 0)
					return null;
				nanos = notEmpty.awaitNanos(nanos);
			}
			return dequeue();
		} finally {
			lock.unlock();
		}
	}

	public ByteBuffer peek() {
		final ReentrantLock lock = this.lock;
		lock.lock();
		try {
			return itemAt(takeIndex); // null when queue is empty
		} finally {
			lock.unlock();
		}
	}

	// this doc comment is overridden to remove the reference to collections
	// greater in size than Integer.MAX_VALUE
	/**
	 * Returns the number of elements in this queue.
	 *
	 * @return the number of elements in this queue
	 */
	public int size() {
		final ReentrantLock lock = this.lock;
		lock.lock();
		try {
			return count;
		} finally {
			lock.unlock();
		}
	}

	// this doc comment is a modified copy of the inherited doc comment,
	// without the reference to unlimited queues.
	/**
	 * Returns the number of additional elements that this queue can ideally (in
	 * the absence of memory or resource constraints) accept without blocking.
	 * This is always equal to the initial capacity of this queue less the
	 * current {@code size} of this queue.
	 *
	 * <p>
	 * Note that you <em>cannot</em> always tell if an attempt to insert an
	 * element will succeed by inspecting {@code remainingCapacity} because it
	 * may be the case that another thread is about to insert or remove an
	 * element.
	 */
	public int remainingCapacity() {
		final ReentrantLock lock = this.lock;
		lock.lock();
		try {
			return items.length - count;
		} finally {
			lock.unlock();
		}
	}

	/**
	 * Removes a single instance of the specified element from this queue, if it
	 * is present. More formally, removes an element {@code e} such that
	 * {@code o.equals(e)}, if this queue contains one or more such elements.
	 * Returns {@code true} if this queue contained the specified element (or
	 * equivalently, if this queue changed as a result of the call).
	 *
	 * <p>
	 * Removal of interior elements in circular array based queues is an
	 * intrinsically slow and disruptive operation, so should be undertaken only
	 * in exceptional circumstances, ideally only when the queue is known not to
	 * be accessible by other threads.
	 *
	 * @param o
	 *            element to be removed from this queue, if present
	 * @return {@code true} if this queue changed as a result of the call
	 */
	public boolean remove(Object o) {
		if (o == null)
			return false;
		final Object[] items = this.items;
		final ReentrantLock lock = this.lock;
		lock.lock();
		try {
			if (count > 0) {
				final int putIndex = this.putIndex;
				int i = takeIndex;
				do {
					if (o.equals(items[i])) {
						removeAt(i);
						return true;
					}
					if (++i == items.length)
						i = 0;
				} while (i != putIndex);
			}
			return false;
		} finally {
			lock.unlock();
		}
	}

	/**
	 * Returns {@code true} if this queue contains the specified element. More
	 * formally, returns {@code true} if and only if this queue contains at
	 * least one element {@code e} such that {@code o.equals(e)}.
	 *
	 * @param o
	 *            object to be checked for containment in this queue
	 * @return {@code true} if this queue contains the specified element
	 */
	public boolean contains(Object o) {
		if (o == null)
			return false;
		final Object[] items = this.items;
		final ReentrantLock lock = this.lock;
		lock.lock();
		try {
			if (count > 0) {
				final int putIndex = this.putIndex;
				int i = takeIndex;
				do {
					if (o.equals(items[i]))
						return true;
					if (++i == items.length)
						i = 0;
				} while (i != putIndex);
			}
			return false;
		} finally {
			lock.unlock();
		}
	}

	/**
	 * Returns an array containing all of the elements in this queue, in proper
	 * sequence.
	 *
	 * <p>
	 * The returned array will be "safe" in that no references to it are
	 * maintained by this queue. (In other words, this method must allocate a
	 * new array). The caller is thus free to modify the returned array.
	 *
	 * <p>
	 * This method acts as bridge between array-based and collection-based APIs.
	 *
	 * @return an array containing all of the elements in this queue
	 */
	public Object[] toArray() {
		Object[] a;
		final ReentrantLock lock = this.lock;
		lock.lock();
		try {
			final int count = this.count;
			a = new Object[count];
			int n = items.length - takeIndex;
			if (count <= n)
				System.arraycopy(items, takeIndex, a, 0, count);
			else {
				System.arraycopy(items, takeIndex, a, 0, n);
				System.arraycopy(items, 0, a, n, count - n);
			}
		} finally {
			lock.unlock();
		}
		return a;
	}

	/**
	 * Returns an array containing all of the elements in this queue, in proper
	 * sequence; the runtime type of the returned array is that of the specified
	 * array. If the queue fits in the specified array, it is returned therein.
	 * Otherwise, a new array is allocated with the runtime type of the
	 * specified array and the size of this queue.
	 *
	 * <p>
	 * If this queue fits in the specified array with room to spare (i.e., the
	 * array has more elements than this queue), the element in the array
	 * immediately following the end of the queue is set to {@code null}.
	 *
	 * <p>
	 * Like the {@link #toArray()} method, this method acts as bridge between
	 * array-based and collection-based APIs. Further, this method allows
	 * precise control over the runtime type of the output array, and may, under
	 * certain circumstances, be used to save allocation costs.
	 *
	 * <p>
	 * Suppose {@code x} is a queue known to contain only strings. The following
	 * code can be used to dump the queue into a newly allocated array of
	 * {@code String}:
	 *
	 * <pre>
	 * {
	 * 	&#64;code
	 * 	String[] y = x.toArray(new String[0]);
	 * }
	 * </pre>
	 *
	 * Note that {@code toArray(new Object[0])} is identical in function to
	 * {@code toArray()}.
	 *
	 * @param a
	 *            the array into which the elements of the queue are to be
	 *            stored, if it is big enough; otherwise, a new array of the
	 *            same runtime type is allocated for this purpose
	 * @return an array containing all of the elements in this queue
	 * @throws ArrayStoreException
	 *             if the runtime type of the specified array is not a supertype
	 *             of the runtime type of every element in this queue
	 * @throws NullPointerException
	 *             if the specified array is null
	 */
	@SuppressWarnings("unchecked")
	public <T> T[] toArray(T[] a) {
		final Object[] items = this.items;
		final ReentrantLock lock = this.lock;
		lock.lock();
		try {
			final int count = this.count;
			final int len = a.length;
			if (len < count)
				a = (T[]) java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), count);
			int n = items.length - takeIndex;
			if (count <= n)
				System.arraycopy(items, takeIndex, a, 0, count);
			else {
				System.arraycopy(items, takeIndex, a, 0, n);
				System.arraycopy(items, 0, a, n, count - n);
			}
			if (len > count)
				a[count] = null;
		} finally {
			lock.unlock();
		}
		return a;
	}

	public String toString() {
		final ReentrantLock lock = this.lock;
		lock.lock();
		try {
			int k = count;
			if (k == 0)
				return "[]";

			final Object[] items = this.items;
			StringBuilder sb = new StringBuilder();
			sb.append('[');
			for (int i = takeIndex;;) {
				Object e = items[i];
				sb.append(e == this ? "(this Collection)" : e);
				if (--k == 0)
					return sb.append(']').toString();
				sb.append(',').append(' ');
				if (++i == items.length)
					i = 0;
			}
		} finally {
			lock.unlock();
		}
	}

	/**
	 * Atomically removes all of the elements from this queue. The queue will be
	 * empty after this call returns.
	 */
	public void clear() {
		final Object[] items = this.items;
		final ReentrantLock lock = this.lock;
		lock.lock();
		try {
			int k = count;
			if (k > 0) {
				final int putIndex = this.putIndex;
				int i = takeIndex;
				do {
					items[i] = null;
					if (++i == items.length)
						i = 0;
				} while (i != putIndex);
				takeIndex = putIndex;
				count = 0;
				if (itrs != null)
					itrs.queueIsEmpty();
				for (; k > 0 && lock.hasWaiters(notFull); k--)
					notFull.signal();
			}
		} finally {
			lock.unlock();
		}
	}

	/**
	 * @throws UnsupportedOperationException
	 *             {@inheritDoc}
	 * @throws ClassCastException
	 *             {@inheritDoc}
	 * @throws NullPointerException
	 *             {@inheritDoc}
	 * @throws IllegalArgumentException
	 *             {@inheritDoc}
	 */
	public int drainTo(Collection<? super ByteBuffer> c) {
		return drainTo(c, Integer.MAX_VALUE);
	}

	/**
	 * @throws UnsupportedOperationException
	 *             {@inheritDoc}
	 * @throws ClassCastException
	 *             {@inheritDoc}
	 * @throws NullPointerException
	 *             {@inheritDoc}
	 * @throws IllegalArgumentException
	 *             {@inheritDoc}
	 */
	public int drainTo(Collection<? super ByteBuffer> c, int maxElements) {
		checkNotNull(c);
		if (c == this)
			throw new IllegalArgumentException();
		if (maxElements <= 0)
			return 0;
		final ByteBuffer[] items = this.items;
		final ReentrantLock lock = this.lock;
		lock.lock();
		try {
			int n = Math.min(maxElements, count);
			int take = takeIndex;
			int i = 0;
			try {
				while (i < n) {
					ByteBuffer x = items[take];
					c.add(x);
					items[take] = null;
					if (++take == items.length)
						take = 0;
					i++;
				}
				return n;
			} finally {
				// Restore invariants even if c.add() threw
				if (i > 0) {
					count -= i;
					takeIndex = take;
					if (itrs != null) {
						if (count == 0)
							itrs.queueIsEmpty();
						else if (i > take)
							itrs.takeIndexWrapped();
					}
					for (; i > 0 && lock.hasWaiters(notFull); i--)
						notFull.signal();
				}
			}
		} finally {
			lock.unlock();
		}
	}

	/**
	 * Returns an iterator over the elements in this queue in proper sequence.
	 * The elements will be returned in order from first (head) to last (tail).
	 *
	 * <p>
	 * The returned iterator is <a href="package-summary.html#Weakly"><i>weakly
	 * consistent</i></a>.
	 *
	 * @return an iterator over the elements in this queue in proper sequence
	 */
	public Iterator<ByteBuffer> iterator() {
		return new Itr();
	}

	/**
	 * Shared data between iterators and their queue, allowing queue
	 * modifications to update iterators when elements are removed.
	 *
	 * This adds a lot of complexity for the sake of correctly handling some
	 * uncommon operations, but the combination of circular-arrays and
	 * supporting interior removes (i.e., those not at head) would cause
	 * iterators to sometimes lose their places and/or (re)report elements they
	 * shouldn't. To avoid this, when a queue has one or more iterators, it
	 * keeps iterator state consistent by:
	 *
	 * (1) keeping track of the number of "cycles", that is, the number of times
	 * takeIndex has wrapped around to 0. (2) notifying all iterators via the
	 * callback removedAt whenever an interior element is removed (and thus
	 * other elements may be shifted).
	 *
	 * These suffice to eliminate iterator inconsistencies, but unfortunately
	 * add the secondary responsibility of maintaining the list of iterators. We
	 * track all active iterators in a simple linked list (accessed only when
	 * the queue's lock is held) of weak references to Itr. The list is cleaned
	 * up using 3 different mechanisms:
	 *
	 * (1) Whenever a new iterator is created, do some O(1) checking for stale
	 * list elements.
	 *
	 * (2) Whenever takeIndex wraps around to 0, check for iterators that have
	 * been unused for more than one wrap-around cycle.
	 *
	 * (3) Whenever the queue becomes empty, all iterators are notified and this
	 * entire data structure is discarded.
	 *
	 * So in addition to the removedAt callback that is necessary for
	 * correctness, iterators have the shutdown and takeIndexWrapped callbacks
	 * that help remove stale iterators from the list.
	 *
	 * Whenever a list element is examined, it is expunged if either the GC has
	 * determined that the iterator is discarded, or if the iterator reports
	 * that it is "detached" (does not need any further state updates). Overhead
	 * is maximal when takeIndex never advances, iterators are discarded before
	 * they are exhausted, and all removals are interior removes, in which case
	 * all stale iterators are discovered by the GC. But even in this case we
	 * don't increase the amortized complexity.
	 *
	 * Care must be taken to keep list sweeping methods from reentrantly
	 * invoking another such method, causing subtle corruption bugs.
	 */
	class Itrs {

		/**
		 * Node in a linked list of weak iterator references.
		 */
		private class Node extends WeakReference<Itr> {
			Node next;

			Node(Itr iterator, Node next) {
				super(iterator);
				this.next = next;
			}
		}

		/** Incremented whenever takeIndex wraps around to 0 */
		int cycles = 0;

		/** Linked list of weak iterator references */
		private Node head;

		/** Used to expunge stale iterators */
		private Node sweeper = null;

		private static final int SHORT_SWEEP_PROBES = 4;
		private static final int LONG_SWEEP_PROBES = 16;

		Itrs(Itr initial) {
			register(initial);
		}

		/**
		 * Sweeps itrs, looking for and expunging stale iterators. If at least
		 * one was found, tries harder to find more. Called only from iterating
		 * thread.
		 *
		 * @param tryHarder
		 *            whether to start in try-harder mode, because there is
		 *            known to be at least one iterator to collect
		 */
		void doSomeSweeping(boolean tryHarder) {
			// assert lock.getHoldCount() == 1;
			// assert head != null;
			int probes = tryHarder ? LONG_SWEEP_PROBES : SHORT_SWEEP_PROBES;
			Node o, p;
			final Node sweeper = this.sweeper;
			boolean passedGo; // to limit search to one full sweep

			if (sweeper == null) {
				o = null;
				p = head;
				passedGo = true;
			} else {
				o = sweeper;
				p = o.next;
				passedGo = false;
			}

			for (; probes > 0; probes--) {
				if (p == null) {
					if (passedGo)
						break;
					o = null;
					p = head;
					passedGo = true;
				}
				final Itr it = p.get();
				final Node next = p.next;
				if (it == null || it.isDetached()) {
					// found a discarded/exhausted iterator
					probes = LONG_SWEEP_PROBES; // "try harder"
					// unlink p
					p.clear();
					p.next = null;
					if (o == null) {
						head = next;
						if (next == null) {
							// We've run out of iterators to track; retire
							itrs = null;
							return;
						}
					} else
						o.next = next;
				} else {
					o = p;
				}
				p = next;
			}

			this.sweeper = (p == null) ? null : o;
		}

		/**
		 * Adds a new iterator to the linked list of tracked iterators.
		 */
		void register(Itr itr) {
			// assert lock.getHoldCount() == 1;
			head = new Node(itr, head);
		}

		/**
		 * Called whenever takeIndex wraps around to 0.
		 *
		 * Notifies all iterators, and expunges any that are now stale.
		 */
		void takeIndexWrapped() {
			// assert lock.getHoldCount() == 1;
			cycles++;
			for (Node o = null, p = head; p != null;) {
				final Itr it = p.get();
				final Node next = p.next;
				if (it == null || it.takeIndexWrapped()) {
					// unlink p
					// assert it == null || it.isDetached();
					p.clear();
					p.next = null;
					if (o == null)
						head = next;
					else
						o.next = next;
				} else {
					o = p;
				}
				p = next;
			}
			if (head == null) // no more iterators to track
				itrs = null;
		}

		/**
		 * Called whenever an interior remove (not at takeIndex) occurred.
		 *
		 * Notifies all iterators, and expunges any that are now stale.
		 */
		void removedAt(int removedIndex) {
			for (Node o = null, p = head; p != null;) {
				final Itr it = p.get();
				final Node next = p.next;
				if (it == null || it.removedAt(removedIndex)) {
					// unlink p
					// assert it == null || it.isDetached();
					p.clear();
					p.next = null;
					if (o == null)
						head = next;
					else
						o.next = next;
				} else {
					o = p;
				}
				p = next;
			}
			if (head == null) // no more iterators to track
				itrs = null;
		}

		/**
		 * Called whenever the queue becomes empty.
		 *
		 * Notifies all active iterators that the queue is empty, clears all
		 * weak refs, and unlinks the itrs datastructure.
		 */
		void queueIsEmpty() {
			// assert lock.getHoldCount() == 1;
			for (Node p = head; p != null; p = p.next) {
				Itr it = p.get();
				if (it != null) {
					p.clear();
					it.shutdown();
				}
			}
			head = null;
			itrs = null;
		}

		/**
		 * Called whenever an element has been dequeued (at takeIndex).
		 */
		void elementDequeued() {
			// assert lock.getHoldCount() == 1;
			if (count == 0)
				queueIsEmpty();
			else if (takeIndex == 0)
				takeIndexWrapped();
		}
	}

	/**
	 * Iterator for ArrayBlockingQueue.
	 *
	 * To maintain weak consistency with respect to puts and takes, we read
	 * ahead one slot, so as to not report hasNext true but then not have an
	 * element to return.
	 *
	 * We switch into "detached" mode (allowing prompt unlinking from itrs
	 * without help from the GC) when all indices are negative, or when hasNext
	 * returns false for the first time. This allows the iterator to track
	 * concurrent updates completely accurately, except for the corner case of
	 * the user calling Iterator.remove() after hasNext() returned false. Even
	 * in this case, we ensure that we don't remove the wrong element by keeping
	 * track of the expected element to remove, in lastItem. Yes, we may fail to
	 * remove lastItem from the queue if it moved due to an interleaved interior
	 * remove while in detached mode.
	 */
	private class Itr implements Iterator<ByteBuffer> {
		/** Index to look for new nextItem; NONE at end */
		private int cursor;

		/** Element to be returned by next call to next(); null if none */
		private ByteBuffer nextItem;

		/** Index of nextItem; NONE if none, REMOVED if removed elsewhere */
		private int nextIndex;

		/** Last element returned; null if none or not detached. */
		private ByteBuffer lastItem;

		/** Index of lastItem, NONE if none, REMOVED if removed elsewhere */
		private int lastRet;

		/** Previous value of takeIndex, or DETACHED when detached */
		private int prevTakeIndex;

		/** Previous value of iters.cycles */
		private int prevCycles;

		/** Special index value indicating "not available" or "undefined" */
		private static final int NONE = -1;

		/**
		 * Special index value indicating "removed elsewhere", that is, removed
		 * by some operation other than a call to this.remove().
		 */
		private static final int REMOVED = -2;

		/** Special value for prevTakeIndex indicating "detached mode" */
		private static final int DETACHED = -3;

		Itr() {
			// assert lock.getHoldCount() == 0;
			lastRet = NONE;
			final ReentrantLock lock = ArrayBlockingQueue.this.lock;
			lock.lock();
			try {
				if (count == 0) {
					// assert itrs == null;
					cursor = NONE;
					nextIndex = NONE;
					prevTakeIndex = DETACHED;
				} else {
					final int takeIndex = ArrayBlockingQueue.this.takeIndex;
					prevTakeIndex = takeIndex;
					nextItem = itemAt(nextIndex = takeIndex);
					cursor = incCursor(takeIndex);
					if (itrs == null) {
						itrs = new Itrs(this);
					} else {
						itrs.register(this); // in this order
						itrs.doSomeSweeping(false);
					}
					prevCycles = itrs.cycles;
					// assert takeIndex >= 0;
					// assert prevTakeIndex == takeIndex;
					// assert nextIndex >= 0;
					// assert nextItem != null;
				}
			} finally {
				lock.unlock();
			}
		}

		boolean isDetached() {
			// assert lock.getHoldCount() == 1;
			return prevTakeIndex < 0;
		}

		private int incCursor(int index) {
			// assert lock.getHoldCount() == 1;
			if (++index == items.length)
				index = 0;
			if (index == putIndex)
				index = NONE;
			return index;
		}

		/**
		 * Returns true if index is invalidated by the given number of dequeues,
		 * starting from prevTakeIndex.
		 */
		private boolean invalidated(int index, int prevTakeIndex, long dequeues, int length) {
			if (index < 0)
				return false;
			int distance = index - prevTakeIndex;
			if (distance < 0)
				distance += length;
			return dequeues > distance;
		}

		/**
		 * Adjusts indices to incorporate all dequeues since the last operation
		 * on this iterator. Call only from iterating thread.
		 */
		private void incorporateDequeues() {
			// assert lock.getHoldCount() == 1;
			// assert itrs != null;
			// assert !isDetached();
			// assert count > 0;

			final int cycles = itrs.cycles;
			final int takeIndex = ArrayBlockingQueue.this.takeIndex;
			final int prevCycles = this.prevCycles;
			final int prevTakeIndex = this.prevTakeIndex;

			if (cycles != prevCycles || takeIndex != prevTakeIndex) {
				final int len = items.length;
				// how far takeIndex has advanced since the previous
				// operation of this iterator
				long dequeues = (cycles - prevCycles) * len + (takeIndex - prevTakeIndex);

				// Check indices for invalidation
				if (invalidated(lastRet, prevTakeIndex, dequeues, len))
					lastRet = REMOVED;
				if (invalidated(nextIndex, prevTakeIndex, dequeues, len))
					nextIndex = REMOVED;
				if (invalidated(cursor, prevTakeIndex, dequeues, len))
					cursor = takeIndex;

				if (cursor < 0 && nextIndex < 0 && lastRet < 0)
					detach();
				else {
					this.prevCycles = cycles;
					this.prevTakeIndex = takeIndex;
				}
			}
		}

		/**
		 * Called when itrs should stop tracking this iterator, either because
		 * there are no more indices to update (cursor < 0 && nextIndex < 0 &&
		 * lastRet < 0) or as a special exception, when lastRet >= 0, because
		 * hasNext() is about to return false for the first time. Call only from
		 * iterating thread.
		 */
		private void detach() {
			// Switch to detached mode
			// assert lock.getHoldCount() == 1;
			// assert cursor == NONE;
			// assert nextIndex < 0;
			// assert lastRet < 0 || nextItem == null;
			// assert lastRet < 0 ^ lastItem != null;
			if (prevTakeIndex >= 0) {
				// assert itrs != null;
				prevTakeIndex = DETACHED;
				// try to unlink from itrs (but not too hard)
				itrs.doSomeSweeping(true);
			}
		}

		/**
		 * For performance reasons, we would like not to acquire a lock in
		 * hasNext in the common case. To allow for this, we only access fields
		 * (i.e. nextItem) that are not modified by update operations triggered
		 * by queue modifications.
		 */
		public boolean hasNext() {
			// assert lock.getHoldCount() == 0;
			if (nextItem != null)
				return true;
			noNext();
			return false;
		}

		private void noNext() {
			final ReentrantLock lock = ArrayBlockingQueue.this.lock;
			lock.lock();
			try {
				// assert cursor == NONE;
				// assert nextIndex == NONE;
				if (!isDetached()) {
					// assert lastRet >= 0;
					incorporateDequeues(); // might update lastRet
					if (lastRet >= 0) {
						lastItem = itemAt(lastRet);
						// assert lastItem != null;
						detach();
					}
				}
				// assert isDetached();
				// assert lastRet < 0 ^ lastItem != null;
			} finally {
				lock.unlock();
			}
		}

		public ByteBuffer next() {
			// assert lock.getHoldCount() == 0;
			final ByteBuffer x = nextItem;
			if (x == null)
				throw new NoSuchElementException();
			final ReentrantLock lock = ArrayBlockingQueue.this.lock;
			lock.lock();
			try {
				if (!isDetached())
					incorporateDequeues();
				// assert nextIndex != NONE;
				// assert lastItem == null;
				lastRet = nextIndex;
				final int cursor = this.cursor;
				if (cursor >= 0) {
					nextItem = itemAt(nextIndex = cursor);
					// assert nextItem != null;
					this.cursor = incCursor(cursor);
				} else {
					nextIndex = NONE;
					nextItem = null;
				}
			} finally {
				lock.unlock();
			}
			return x;
		}

		public void remove() {
			// assert lock.getHoldCount() == 0;
			final ReentrantLock lock = ArrayBlockingQueue.this.lock;
			lock.lock();
			try {
				if (!isDetached())
					incorporateDequeues(); // might update lastRet or detach
				final int lastRet = this.lastRet;
				this.lastRet = NONE;
				if (lastRet >= 0) {
					if (!isDetached())
						removeAt(lastRet);
					else {
						final ByteBuffer lastItem = this.lastItem;
						// assert lastItem != null;
						this.lastItem = null;
						if (itemAt(lastRet) == lastItem)
							removeAt(lastRet);
					}
				} else if (lastRet == NONE)
					throw new IllegalStateException();
				// else lastRet == REMOVED and the last returned element was
				// previously asynchronously removed via an operation other
				// than this.remove(), so nothing to do.

				if (cursor < 0 && nextIndex < 0)
					detach();
			} finally {
				lock.unlock();
				// assert lastRet == NONE;
				// assert lastItem == null;
			}
		}

		/**
		 * Called to notify the iterator that the queue is empty, or that it has
		 * fallen hopelessly behind, so that it should abandon any further
		 * iteration, except possibly to return one more element from next(), as
		 * promised by returning true from hasNext().
		 */
		void shutdown() {
			// assert lock.getHoldCount() == 1;
			cursor = NONE;
			if (nextIndex >= 0)
				nextIndex = REMOVED;
			if (lastRet >= 0) {
				lastRet = REMOVED;
				lastItem = null;
			}
			prevTakeIndex = DETACHED;
			// Don't set nextItem to null because we must continue to be
			// able to return it on next().
			//
			// Caller will unlink from itrs when convenient.
		}

		private int distance(int index, int prevTakeIndex, int length) {
			int distance = index - prevTakeIndex;
			if (distance < 0)
				distance += length;
			return distance;
		}

		/**
		 * Called whenever an interior remove (not at takeIndex) occurred.
		 *
		 * @return true if this iterator should be unlinked from itrs
		 */
		boolean removedAt(int removedIndex) {
			// assert lock.getHoldCount() == 1;
			if (isDetached())
				return true;

			final int cycles = itrs.cycles;
			final int takeIndex = ArrayBlockingQueue.this.takeIndex;
			final int prevCycles = this.prevCycles;
			final int prevTakeIndex = this.prevTakeIndex;
			final int len = items.length;
			int cycleDiff = cycles - prevCycles;
			if (removedIndex < takeIndex)
				cycleDiff++;
			final int removedDistance = (cycleDiff * len) + (removedIndex - prevTakeIndex);
			// assert removedDistance >= 0;
			int cursor = this.cursor;
			if (cursor >= 0) {
				int x = distance(cursor, prevTakeIndex, len);
				if (x == removedDistance) {
					if (cursor == putIndex)
						this.cursor = cursor = NONE;
				} else if (x > removedDistance) {
					// assert cursor != prevTakeIndex;
					this.cursor = cursor = dec(cursor);
				}
			}
			int lastRet = this.lastRet;
			if (lastRet >= 0) {
				int x = distance(lastRet, prevTakeIndex, len);
				if (x == removedDistance)
					this.lastRet = lastRet = REMOVED;
				else if (x > removedDistance)
					this.lastRet = lastRet = dec(lastRet);
			}
			int nextIndex = this.nextIndex;
			if (nextIndex >= 0) {
				int x = distance(nextIndex, prevTakeIndex, len);
				if (x == removedDistance)
					this.nextIndex = nextIndex = REMOVED;
				else if (x > removedDistance)
					this.nextIndex = nextIndex = dec(nextIndex);
			} else if (cursor < 0 && nextIndex < 0 && lastRet < 0) {
				this.prevTakeIndex = DETACHED;
				return true;
			}
			return false;
		}

		/**
		 * Called whenever takeIndex wraps around to zero.
		 *
		 * @return true if this iterator should be unlinked from itrs
		 */
		boolean takeIndexWrapped() {
			// assert lock.getHoldCount() == 1;
			if (isDetached())
				return true;
			if (itrs.cycles - prevCycles > 1) {
				// All the elements that existed at the time of the last
				// operation are gone, so abandon further iteration.
				shutdown();
				return true;
			}
			return false;
		}

		// /** Uncomment for debugging. */
		// public String toString() {
		// return ("cursor=" + cursor + " " +
		// "nextIndex=" + nextIndex + " " +
		// "lastRet=" + lastRet + " " +
		// "nextItem=" + nextItem + " " +
		// "lastItem=" + lastItem + " " +
		// "prevCycles=" + prevCycles + " " +
		// "prevTakeIndex=" + prevTakeIndex + " " +
		// "size()=" + size() + " " +
		// "remainingCapacity()=" + remainingCapacity());
		// }
	}

	/**
	 * Returns a {@link Spliterator} over the elements in this queue.
	 *
	 * <p>
	 * The returned spliterator is
	 * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
	 *
	 * <p>
	 * The {@code Spliterator} reports {@link Spliterator#CONCURRENT},
	 * {@link Spliterator#ORDERED}, and {@link Spliterator#NONNULL}.
	 *
	 * @implNote The {@code Spliterator} implements {@code trySplit} to permit
	 *           limited parallelism.
	 *
	 * @return a {@code Spliterator} over the elements in this queue
	 * @since 1.8
	 */
	public Spliterator<ByteBuffer> spliterator() {
		return Spliterators.spliterator(this, Spliterator.ORDERED | Spliterator.NONNULL | Spliterator.CONCURRENT);
	}

}
